package com.zhugang.week07;

/**
 * @program algorithms
 * @description: myHeap
 * @author: chanzhugang
 * @create: 2022/08/01 15:04
 */
public class MyHeap {

    private int a[];
    private int n;
    private int count;

    public MyHeap(int capacity) {
        a = new int[capacity + 1];
        n = capacity;
        count = 0;
    }

    /**
     * 插入元素：插入末尾，从下往上堆化
     *
     * @param data
     */
    public void insert(int data) {
        if (count >= n) {
            return;
        }
        count++;
        a[count] = data;
        int i = count;
        while (i / 2 > 0 && a[i] > a[i / 2]) {
            // 自下而上堆化
            swap(a, i, i / 2);
            i = i / 2;
        }
    }

    /**
     * 取堆顶元素
     *
     * @return
     */
    public int top() {
        if (count == 0) {
            return Integer.MIN_VALUE;
        }
        return a[1];
    }

    /**
     * 删除堆顶元素：最后一个元素放到堆顶，自上而下堆化
     */
    public void removeTop() {
        if (count == 0) {
            return;
        }
        a[1] = a[count];
        count--;
        heapify(a, count, 1);
    }

    /**
     * 自上而下堆化
     *
     * @param a
     * @param n
     * @param i
     */
    private void heapify(int[] a, int n, int i) {
        while (true) {
            int maxPos = i;
            if (i * 2 <= n && a[i] < a[i * 2]) {
                maxPos = i * 2;
            }
            if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) {
                maxPos = i * 2 + 1;
            }
            if (maxPos == i) {
                break;
            }
            swap(a, i, maxPos);
            i = maxPos;
        }
    }

    /**
     * 建堆：从右往左处理，每个元素自上而下堆化
     *
     * @param a
     * @param n
     */
    public void buildHeap(int[] a, int n) {
        for (int i = n / 2; i >= 1; i--) {
            heapify(a, n, i);
        }
    }

    /**
     * 堆排序
     *
     * @param a
     * @param n
     */
    public void sort(int[] a, int n) {
        buildHeap(a, n);
        int k = n;
        while (k > 1) {
            swap(a, 1, k);
            --k;
            heapify(a, k, 1);
        }
    }


    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}